Data Structure--Priority Queue

发表于 | 分类于 | 阅读次数
字数统计 1,587 | 阅读时长 9

Data Structure--Priority Queue

  • Collection : Insert and delete items.

But Which item to delete?

  1. Stack. Remove the item most recently added

  2. Queue. Remove the imte least recently added

  3. Randomized queue. Remove a random item

  4. Priority queue. Remove the largest (or smallest) item.

APIs:

public class MaxPQ<Key extends Comparable <Key>>

Image Title

Image Title Challenge. Find the lagest M items in a stream of N items Image Title

优先队列的无序数组实现形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
    import static java.lang.System.out;
    
    import java.util.NoSuchElementException;
    
    /**
     * Implements a <i>Priority Queue</i> unordered that iterates over the largest key.
     * 
     * <h5>Lecture: APIs and Elementary Implementations (Week 4)</h5>
     * 
     * <p>
     *  Keep the entries unordered in an resizing array, when method <code>delMax<code> 
     *  is called it remove and return the largest key.
     * </p>
     * 
     * @see MaxPQ.java
     * @author eder.magalhaes
     * @param <Key> parameterized type for key.
     */
    public class UnorderedMaxPQ<Key extends Comparable<Key>> {
    
        private Key[] pq;
        private int N;
        
        public UnorderedMaxPQ() {
        	this(1);
        }
        
        @SuppressWarnings("unchecked")    
        public UnorderedMaxPQ(int capacity) {
            pq = (Key[]) new Comparable[capacity];
        }
        
        public boolean isEmpty() {
            return N == 0;
        }
        
        public void insert(Key k) {
        	if (N == pq.length - 1) //resize if outbound
        	    resize(2 * pq.length);
        	
            pq[N++] = k;
        }
        
        //linear (N) running time
        public Key delMax() {
        	if (isEmpty()) 
        	    throw new NoSuchElementException();
            
        	int max = 0;
            for (int i = 1; i < N; i++)
                if (less(max, i))
                    max = i;            //遍历取Max
            
            exch(max, N-1);     //把最大值放在队尾，并返回
            Key k = pq[--N];  
            pq[N] = null;
            
            if ((N > 0) && (N == (pq.length - 1) / 4))  //小于队列4分之一是进行resize
                resize(pq.length  / 2);
                return k;
        }
        
        private boolean less(int i, int j) {
        	return pq[i].compareTo(pq[j]) < 0;
        }
        
        private void exch(int i, int j) {
            Key swap = pq[i];
            pq[i] = pq[j];
            pq[j] = swap;
        }
        
        private void resize(int capacity) {
            @SuppressWarnings("unchecked")
            Key[] copy = (Key[]) new Comparable[capacity];
            
            for (int i = 0; i <= N; i++) 
                copy[i] = pq[i];
            
            pq = copy;
        }
        
        public static void main(String[] args) {
            UnorderedMaxPQ<String> queue = new UnorderedMaxPQ<String>(15);
            queue.insert("P");
            queue.insert("R");
            queue.insert("I");
            queue.insert("O");
            queue.insert("R");
            queue.insert("I");
            queue.insert("T");
            queue.insert("Y");
            queue.insert("Q");
            queue.insert("U");
            queue.insert("E");
            queue.insert("U");
            queue.insert("E");
            while (!queue.isEmpty()) {  
                out.printf("%s ", queue.delMax());
            }
        }
    }
```    
优先队列数组的实现形式的算法复杂度是这样的：            
![Image Title](/_image/2014-07-19/4.png)
 无序数组的insert 和delmax的复杂度分别为1和N ，有没有可能实现logN的复杂度呢？有，那就是binary Heap！ 
 
##binary Heap      
1. Binary heap .   Array representation of a heap-ordered complete binary tree.堆序排列的完全二叉树
 *  所谓堆序排列的完整二叉树：
    * Keys in nodes
    * 父节点不比子节点小
 *   所谓数组呈现：
    *从1开始索引
    *水平顺序上实现节点
    *不需要显示的链表
 *  几点假设：Key a[1] 是最大的元素，也是二叉树的根节点
                可以使用数组下标来遍历二叉树
                对于节点K的父节点为K/2
                对于节点K的子节点为2K和2K+1
* 场景1：子节点出现比父节点要大的情况
* 改变方法： 子节点和父节点交换位置，在和该父节点的父节点比较，直到到根节点
```java
        private void swim(int k){
            while (k>1&&less(k/2,k)){
                exch(k/2,k);
                k=k/2;
            }
        }
```            
    
 * 场景2：插入一个数
 * 方法：在数组尾部加一个数，然后swim up,比较次书为1+lgN
```java
        private void insert(int k){
            pq[N++]=k;
            swim(N);        
        }   
```        
  * 场景3：父节点比自己点要小
  * 方法：  交换父节点与子节点中较大的一个，迭代直到队尾或者不出现这种现象为止 
  ```java   
              private void sink(int k){
                while (2*k<N){          //注意越界条件
                    int j=2*k;
                    //j =(less(j,j+1)?j+1:j);//litter trick 与大的值换
                    if(j<N&&less(j,j+1)) j++;
                    if (!less(k,j)) break;
                    exch(k,j);
                    k=j;       
                }  
              }
```              
  * 场景4：删除最大节点，即父节点
  * 方法：父节点与最末节点换位置，然后吧最末节点从最高层sink下来
```java
        public Key delMax(){
            Key max = pq[1];
            exch(1,N--);
            sink(1);
            pq[N+1]=null;
            return Max;        
        }

最后我们可以写出整个PQ类的程序： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
import static java.lang.System.out;
import java.util.NoSuchElementException;
/**
 * Implements a <i>Priority Queue</i> ordered that iterates over the largest key.
 * 
 * <h5>Lecture: APIs and Elementary Implementations (Week 4)</h5>
 * 
 * <p>
 *  Keep the entries ordered in an resizing array.
 * </p>
 * 
 * <p>This colecttion uses <i>Binary heap</i> algorithm.</p>
 * 
 * @see UnorderedMaxPQ.java
 * @author eder.magalhaes
 * @param <Key> parameterized type for key.
 */
public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    
    public MaxPQ() {
    	this(1);
    }
    
    @SuppressWarnings("unchecked")
	public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity+1];
    }
    
    public boolean isEmpty() {
        return N == 0;
    }
    
    public void insert(Key x) {
    	if (N == pq.length - 1) 
    	    resize(2 * pq.length);
    	
        pq[++N] = x;
        swim(N);
    }
    
    public Key delMax() {
    	if (isEmpty()) 
    	    throw new NoSuchElementException();
    	
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        
        pq[N+1] = null;
        
        if ((N > 0) && (N == (pq.length - 1) / 4)) 
            resize(pq.length  / 2);
        
        return max;
    }
    
    //node promoted to level of incompetence (Binary heap);
    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k, k / 2);
            k = k / 2;
        }
    }
    
    //better subordinate (child) promoted (Binary heap);
    private void sink(int k) {
        while (2 * k <= N) {
            int j = 2 * k;
            
            if (j < N && less(j, j+ 1))
                j++;
            
            if (!less(k, j))
                break;
            
            exch(k, j);
            k = j;
        }
    }
    
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
    
    private void exch(int i, int j) {
        Key swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }
    
    private void resize(int capacity) {
        @SuppressWarnings("unchecked")
        Key[] copy = (Key[]) new Comparable[capacity];
        
        for (int i = 1; i <= N; i++) 
            copy[i] = pq[i];
        
        pq = copy;
    }
    
    public static void main(String[] args) {
    	MaxPQ<String> queue = new MaxPQ<String>();
    	queue.insert("P");
        queue.insert("R");
        queue.insert("I");
        queue.insert("O");
        queue.insert("R");
        queue.insert("I");
        queue.insert("T");
        queue.insert("Y");
        queue.insert("Q");
        queue.insert("U");
        queue.insert("E");
        queue.insert("U");
        queue.insert("E");
        
        while (!queue.isEmpty()) {
            out.printf("%s ", queue.delMax());
        }
    }
}

Heapsort

最后介绍基于binary heap的heapsort： basic plan：

  • 先把二叉树变成heapsort，即父节点大于子节点
  • repeatly delete the max key 代码入下： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    import static java.lang.System.out;
    /**
     * Implements a <i>Heapsort</i>.
     * 
     * <h5>Lecture: Heapsort (Week 4)</h5>
     * 
     * <p>
     *  Worst case this algorithms works in 2 N lg N running time.
     *  Best case works in N lg N running time. 
     * </p>
     * 
     * <p>
     *  Faster than Selection, Insertion, Shell, Quick and 3-way quick.
     *  But slow than Mergesort.
     * </p>
     * 
     * @author eder.magalhaes
     */
    public class Heap {
        private static void sink (Comparable[] pq, int k, int N) {
        	while (2 * k <= N) {
        	    int j = 2 * k;
        	    if (j < N && less(pq, j, j+1))
        	        j++;
        		
        	    if (!less(pq, k, j))
        	        break;
        		
        	    exch(pq, k, j);
        	    k = j;
        	}
        }
        
        private static void exch(Object[] pq, int i, int j) {
            Object swap = pq[i-1];
            pq[i-1] = pq[j-1];
            pq[j-1] = swap;
        }
        private static boolean less(Comparable[] pq, int i, int j) {
            return pq[i-1].compareTo(pq[j-1]) < 0;
        }
        
        public static void sort(Comparable[] pq) {
        	int N = pq.length;
        	
        	for (int k = N/2; k >= 1; k--) //此处从数组最后一个父节点，即最后一个节点                          // 的父节点开始，遍历节点，使得整个数组为heap-sorted
        	    sink(pq, k, N);
        	
        	while (N > 1) {
        	    exch(pq, 1, N--);//把最大的放到末尾，把N-1的元素放到树顶去sink
        	    sink(pq, 1, N);//重复做
        	}
        }
        
        public static void main(String[] args) {
        	Integer[] data = new Integer[] {95, 29, 57, 82, 41, 83, 52, 21, 94, 79};
            sort(data);
            
            out.print("Array sorted by Heapsort: ");
            for (Integer x: data) {
                out.printf("%s ",x);
            }
        }
    }

复杂度比较

Significance. In-place sorting algorithm with** N log N worst-case.**

Mergesort: no, linear extra space. Quicksort : no, quadratic time in worst case. Heapsort: yes!

Bottom line. Heapsort is optimal for both time and space, but: Inner loop longer than quicksort’s. Makes poor use of cache memory. Not stable.

summary

Image Title

请我喝杯咖啡吧！